|
In logic circuits, the Toffoli gate (also CCNOT gate), invented by Tommaso Toffoli, is a universal reversible logic gate, which means that any reversible circuit can be constructed from Toffoli gates. It is also known as the "controlled-controlled-not" gate, which describes its action. It has 3-bit inputs and outputs; if the first two bits are set, it inverts the third bit, otherwise all bits stay the same. == Background == A logic gate ''L'' is reversible if, for any output ''y'', there is a unique input ''x'' such that applying ''L''(''x'') = ''y''. If a gate ''L'' is reversible, there is an inverse gate ''L''′ which maps ''y'' to ''x'' for which ''L''′(''y'') = ''x''. From common logic gates, NOT is reversible, as can be seen from its truthtable below. The common AND gate is not reversible however. The inputs 00, 01 and 10 are all mapped to the output 0. Reversible gates have been studied since the 1960s. The original motivation was that reversible gates dissipate less heat (or, in principle, no heat). In a normal gate, input states are lost, since less information is present in the output than was present at the input. This loss of information loses energy to the surrounding area as heat, because of thermodynamic entropy. Another way to understand this is that charges on a circuit are grounded and thus flow away, taking a small quantity of energy with them when they change state. A reversible gate only moves the states around, and since no information is lost, energy is conserved. More recent motivation comes from quantum computing. Quantum mechanics requires the transformations to be reversible but allows more general states of the computation (superpositions). Thus, the reversible gates form a subset of gates allowed by quantum mechanics and, if we can compute something reversibly, we can also compute it on a quantum computer. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Toffoli gate」の詳細全文を読む スポンサード リンク
|